#leetcode题目76：最小覆盖字串
#难度：困难
#时间复杂度：O(n)
#空间复杂度：O(1)
#方法：滑动窗口

from typing import List
import collections
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t:
            return ""
        needcnt=len(t)
        need=collections.defaultdict(int) #使用defaultdict初始化字典
        res=(0,float('inf'))#初始化结果

        for c in t:
            need[c]+=1

        i=0
        for j,c in enumerate(s):
            if need[c]>0:
                needcnt-=1
            need[c]-=1
            if needcnt==0:
                while True:
                    c=s[i]
                    if need[c]==0:
                        break
                    need[c]+=1
                    i+=1
                
                if j-i<res[1]-res[0]:
                    res=(i,j)
                need[s[i]]+=1
                needcnt+=1
                i+=1
        return "" if res[1]>len(s) else s[res[0]:res[1]+1]
            
#测试数据
s="ADOBECODEBANC"
t="ABC"
#预期输出："BANC"
solution=Solution()
print(solution.minWindow(s,t))

